package PersonStu.siqi;

/**
 * @Author: Dijah
 * @Date: 2023/7/21 15:59
 * @Desc: 给定一个正数的矩阵，求子矩阵的最大累加和
 *
 *
 * -90,48,78
 * 64,-40,64
 * -81,-7,66
 */
public class code06_SubMatrixArray {

    public static int maxSum(int [][] m){
        if(m == null || m.length == 0 || m[0].length == 0){
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int cur = 0;
        int [] s = null;
        for(int i =0; i != m.length; i++){//开始的行号
            s = new int[m[0].length];
            for(int j = i; j != m.length; j++){
                //结束的行号j,i~j行是要讨论的范围
                cur = 0;
                //一维数组中找最大子数组的和
                for(int k =0; k != s.length;k++){
                    s[k] += m[j][k];
                    cur += s[k];
                    max = Math.max(max,cur);
                    cur = cur < 0 ? 0 : cur;
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int [][] matrix = {{-90,48,78},{64,-40,64},{-81,-7,66}};
        System.out.println(maxSum(matrix));
    }
}
